package leetcode.code2182;

import java.util.PriorityQueue;

class Solution {
	public String repeatLimitedString(String s, int repeatLimit) {
		int[] dics = new int[26];
		char[] cs = s.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			dics[cs[i] - 'a']++;
		}
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
		for (int i = 25; i >= 0; i--) {
			int size = dics[i];
			if (size > 0) {
				pq.add(new int[] { i, size });
			}
		}
		StringBuffer sb = new StringBuffer();
		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int size = cur[1];
			char c = (char) (cur[0] + 'a');
			while (size > 0) {
				int add = Math.min(repeatLimit, size);
				for (int i = 0; i < add; i++) {
					sb.append(c);
				}
				size -= add;
				if (size > 0) {
					if (!pq.isEmpty()) {
						int[] p = pq.poll();
						sb.append((char) (p[0] + 'a'));
						if (p[1] > 1) {
							p[1] -= 1;
							pq.add(p);
						}
					} else {
						break;
					}
				}
			}
		}
		return sb.toString();
	}
}
